//建立一个单链表，要求实现插入和删除功能
//要求头节点不存储链表内容，仅作为链表的引索
//要求从链表的尾部插入元素，可以构建一个尾指针，但本身不在链表内
//要求查找某一个元素时，返回这个元素的下标
//要求删除某一个元素时，每次删除遍历所有元素并输出。
//要求链表的长度和元素个数可以动态变化。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

class SingleLinkedList {
public:
    Node* head;
    int length;
    SingleLinkedList() {
        head = NULL;
        length = 0;
    }
    ~SingleLinkedList() {
        Node* p = head;
        while (p) {
            Node* q = p->next;
            delete p;
            p = q;
        }
    }
    void insert(int data) {
        Node* newNode = new Node;
        newNode->data = data;
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
        } else {
            Node* p = head;
            while (p->next) {
                p = p->next;
            }
            p->next = newNode;
        }
        length++;
    }
    void deleteNode(int data) {
        Node* p = head;
        Node* q = NULL;
        while (p) {
            if (p->data == data) {
                if (q == NULL) {
                    head = p->next;
                } else {
                    q->next = p->next;
                }
                delete p;
                length--;
                return;
            }
            q = p;
            p = p->next;
        }
        cout << "No such element in the list." << endl;
    }
    int find(int data) {
        int index = 0;
        Node* p = head;
        while (p) {
            if (p->data == data) {
                return index;
            }
            index++;
            p = p->next;
        }
        return -1;
    }
    void print() {
        Node* p = head;
        while (p) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
};

int main() {
    SingleLinkedList list;
    //建表，用循环结构插入元素
    for (int i = 1; i <= 5; i++) {
        list.insert(i);
    }
    list.print();
    list.deleteNode(3);
    list.print();
    cout << "Length: " << list.length << endl;
    cout << "Index of 4: " << list.find(4)+1 << endl;
    return 0;
}